package com.cwj.lab4.查找.散列表;

import com.cwj.lab1.myArrayList;
import com.cwj.lab4.Tool;

import java.util.Objects;

/**
 * 哈希表
 * 链地址冲突处理实现
 * */

public class Hash_table<E, T> implements Hash<E, T> {
    //映射结点，其存储关键字以及其对应的值
    public static class Node<E, T> {
        public E key;//关键字
        public T data;//数据域
        //有key计算处理的哈希码，其中哈希码是没有经过取余运算的，
        // 其在加入哈希表时被设置，而在线性表表扩容时，结点迁移过程，可以减少哈希值计算的重复
        public Integer code;

        public Node(E key, T data, Integer code) {
            this.key = key;
            this.data = data;
            this.code = code;
        }

        //重写该函数，用于使结点的对比仅仅被关键字或是code影响，而不受数据域影响
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;//若为自身比较
            if (o == null || getClass() != o.getClass()) return false;//传入的对象的类为空或是类别都不一样
            Node<?, ?> node = (Node<?, ?>) o;
            //如果code不为空，那么就比较code,否则就比较key
            if (((Node<?, ?>) o).code != null && this.code != null) {
                return this.code.equals(((Node<?, ?>) o).code);
            }
            return key.equals(node.key);
        }

        //计算哈希值
        @Override
        public int hashCode() {
            return Objects.hash(key);
        }
    }

    //一个存储结点线性表的线性表
    private myArrayList<myArrayList<Node<E, T>>> hashList;
    //映射个数
    int len;
    //目前每个索引对应元素个数最大的值
    int maxOne;
    //线性表有用的长度，其值为质数，为了减少冲突
    int p = 0;

    //默认的线性表长度为10;
    public Hash_table() {
        this(10);
    }

    //有参构造器
    public Hash_table(int size) {
        len = 0;
        maxOne = 0;
        hashList = new myArrayList<>(size);
        //这个函数被我封装在我的工具类Tool里面，作用为计算不大于传入的值的最大质数
        this.p = Tool.caluP(size - 1);
        for (int i = 0; i < size; i++) {
            hashList.addLast(new myArrayList<>());
        }
    }

    /**
     * 查找功能
     * @param key 关键字
     * @return 返回对应的数据域，如果不存在返回空
     */
    @Override
    public T find(E key) {
        int code = Math.abs(key.hashCode()) % this.p;
//        System.out.println("code="+code);
        //其中这里的find函数是线性表到顺序查找函数
        int ind = this.hashList.get(code).find(new Node<E, T>(key, null, null));
        if (ind == -1) {
            return null;
        } else {
            return this.hashList.get(code).get(ind).data;
        }
    }
/**
 * 设置结点，即如果存在就修改，否则就是添加
 * 可以看作下面那个函数的限制类
 * @param key   关键字
 * @param data  数据域
 * */
    @Override
    public boolean set(E key, T data) {
        len += 1;
        resize();//扩容，其但不会每次都扩，其有一定的策略
        return this.set(this.hashList, key, data);
    }
    public boolean set(myArrayList<myArrayList<Node<E, T>>> sumList, E key, T data) {
        int codeHash = Math.abs(key.hashCode());
        int code = codeHash % this.p;//取余
        myArrayList<Node<E, T>> list = sumList.get(code);
        //查找关键字是否存在
        int ind = list.find(new Node<>(key, null, codeHash));
        //分类讨论
        if (ind == -1) {
            list.addLast(new Node<>(key, data, codeHash));
            if (this.maxOne < list.size()) {
                this.maxOne = list.size();
            }
            return true;
        } else {
            list.get(ind).data = data;
            return false;
        }
    }
//扩容
    private void resize() {
        //如果有预估索引的线性表长度大于p或是全部元素数目大于5*p,那么就可以扩容
        if (maxOne > this.p || this.len > 5 * p) {
            //System.out.println("resize");
            resize(this.hashList.size() * 2);
        }
    }
    private void resize(int size) {
        myArrayList<myArrayList<Node<E, T>>> oldList = this.hashList;
        this.hashList = this.preResize(size);
        int oldP = this.p;
        this.p = Tool.caluP(size);
//        System.out.println("resize后p=" + this.p);
        //扩容是必须把原有的结点，添加到新表中
        for (int i = 0; i < oldP; i += 1) {
            myArrayList<Node<E, T>> list = oldList.get(i);
            for (int j = 0; j < list.size(); j++) {
                Node<E, T> nn = list.get(j);
                this.set(this.hashList, nn.key, nn.data);
            }
        }
    }
//其是用来封装扩容函数的代码，避免一个函数的代码过大，功能太杂
    private myArrayList<myArrayList<Node<E, T>>> preResize(int size) {
        int pp = Tool.caluP(size);
        System.out.println("preReisze.p=" + pp);
        myArrayList<myArrayList<Node<E, T>>> list = new myArrayList<>(size);
        for (int i = 0; i < pp; i++) {
            list.addLast(new myArrayList<>());
        }
        return list;
    }
//输出函数
    public void show() {
        myArrayList<Node<E, T>> list = null;
        Node<E, T> nn = null;
        System.out.print("{");
        for (int i = 0; i < this.p; i++) {
            list = this.hashList.get(i);
            for (int j = 0; j < list.size(); j++) {
                nn = list.get(j);
                System.out.print("(key=" + nn.key + ",val=" + nn.data + ") ");
            }
        }
        System.out.println("}");
    }
//下面为getter函数
    public int getP() {
        return p;
    }

    public int size() {
        return len;
    }

    public static void main(String[] args) {

    }


}
